//给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [0,1]
//输出: 2
//说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。 
//
// 示例 2: 
//
// 
//输入: nums = [0,1,0]
//输出: 2
//说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// nums[i] 不是 0 就是 1 
// 
//
// Related Topics 数组 哈希表 前缀和 👍 586 👎 0


package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * 连续数组
 * @date 2022-09-27 08:59:37
 */
class P525_ContiguousArray{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P525_ContiguousArray().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findMaxLength(int[] nums) {
		//将原数组的0全部变为-1 则问题等价于“元素值总和为0的连续数组” 接着遍历数组 记录当前的前缀和的值 若该前缀和的值已出现过 则说明标记中的下标到当前扫描的下标的这段数组的总和值是为0的
		//官方题解的评论
		int sum = 0,res = 0;
		//把0换成-1
		for (int i = 0; i < nums.length; i++) {
			if(nums[i] == 0){
				nums[i] = -1;
			}
		}
		//使用map存储数值和以及数组长度
		Map<Integer,Integer> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
			if(sum == 0 && i > res){
				res = i+1;
			}
			if(map.containsKey(sum)){
				res = Math.max(i - map.get(sum),res);
			}else{
				map.put(sum,i);
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
